package com.aikon.wht.paoshan.alg;

import java.util.List;

/**
 * 回文子串
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfHuiwenzichuan {

    // 1.中心扩散法 时间复杂度 O(n*n)


    // http://www.cxyxiaowu.com/2869.html

    /**
     * 马拉车算法 时间复杂度 O(n)
     *
     * @param s
     * @return
     */
    public static String manacher(String s) {
        if (s.length() < 2) {
            return s;
        }
        // 第一步：预处理，将原字符串转换为新字符串
        String t = "^";
        for (int i = 0; i < s.length(); i++) {
            t += "#" + s.charAt(i);
        }
        // 尾部再加上字符@，变为奇数长度字符串
        t += "#$";
        // 第二步：计算数组p、起始索引、最长回文半径
        int n = t.length();
        // p数组
        int[] p = new int[n];
        int id = 0, mx = 0;
        // 最长回文子串的长度
        int maxLength = -1;
        // 最长回文子串的中心位置索引
        int index = 0;
        for (int j = 1; j < n - 1; j++) {
            if (mx > j) {
                p[j] = Math.min(p[2 * id - j], mx - j);
                System.out.println("mx=" + mx + " j=" + j + " id=" + id + " maxLength=" + maxLength + " index=" + index + " p[j]=" + p[j] + " a");
            } else {
                p[j] = 1;
                System.out.println("mx=" + mx + " j=" + j + " id=" + id + " maxLength=" + maxLength + " index=" + index + " p[j]=" + p[j] + " b");
            }
            // 向左右两边延伸，扩展右边界
            while (t.charAt(j + p[j]) == t.charAt(j - p[j])) {
                p[j]++;
                System.out.println("mx=" + mx + " j=" + j + " id=" + id + " maxLength=" + maxLength + " index=" + index + " p[j]=" + p[j] + " c");
            }
            // 如果回文子串的右边界超过了mx，则需要更新mx和id的值
            if (mx < p[j] + j) {
                mx = p[j] + j;
                id = j;
                System.out.println("mx=" + mx + " j=" + j + " id=" + id + " maxLength=" + maxLength + " index=" + index + " p[j]=" + p[j] + " d");
            }
            // 如果回文子串的长度大于maxLength，则更新maxLength和index的值
            if (maxLength < p[j] - 1) {
                maxLength = p[j] - 1;
                index = j;
                System.out.println("mx=" + mx + " j=" + j + " id=" + id + " maxLength=" + maxLength + " index=" + index + " p[j]=" + p[j] + " e");
            }
        }
        // 第三步：截取字符串，输出结果
        // 起始索引的计算参看前文第四部分
        System.out.println("mx=" + mx + " id=" + id + " maxLength=" + maxLength + " index=" + index + " f");
        int start = (index - maxLength) / 2;
        return s.substring(start, start + maxLength);
    }

    public static void main(String[] args) {
        System.out.println(manacher("cabbaf"));
    }

//        0 1 2 3 4 5 6
//        # a # b # a #
//        1 2 1 4 1 2 1
//
//        0 1 2 3 4 5 6 7 8 9 10 11 12
//        # c # a # b # b # a #  f  #
//        1 2 1 2 1 2 5 2 1 2 1  2  1

//      0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
//      ^ # c # a # b # b # a  #  f  #  $
//      1 1 2 1 2 1 2 5 2 1 2  1  2  1  1
}
